Prim's Algorithm

Prim's Algorithm is a popular and efficient greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. This algorithm helps to find a subset of the graph's edges that forms a tree including every vertex, where the total weight of all the edges in the tree is minimized.

Algorithm Workflow

1. Initialization:

   • Start with an arbitrary node as the root of the MST.
   • Initialize a priority queue (or min-heap) that stores edges based on their weights.

2. Building the MST:

   • Add the initial node to the MST.
   • Insert all edges connected to this node into the priority queue.
   • While the priority queue is not empty:
     • Extract the minimum weight edge from the priority queue.
     • If the edge connects a node outside the MST, add this node to the MST and the edge to the MST result.
     • Add all edges connected to this newly included node (but not already in the MST) to the priority queue.

3. Completion:

   • Repeat until all nodes are included in the MST.

Pseudo Code

function PrimsAlgorithm(G, start):
    Initialize:
        MST_Set = {}               // Set to store the nodes included in the MST
        Edge_List = empty          // List to store edges of the MST
        Min_Heap = empty           // Priority queue to store the edges based on weight

    Add start node to MST_Set
    Add all edges from start node to Min_Heap

    while Min_Heap is not empty:
        edge = Min_Heap.extract_min()   // Remove and get the edge with the smallest weight
        if edge.node2 not in MST_Set:
            Add edge to Edge_List
            Add edge.node2 to MST_Set
            for each edge connected to edge.node2:
                if edge.destination not in MST_Set:
                    Min_Heap.add(edge.destination, edge.weight)

    return Edge_List

Key Properties

• Prim's algorithm works similarly to Dijkstra's algorithm but focuses on edge weights for MST construction rather than shortest path finding.
• The algorithm can handle graphs with negative edge weights without any problems.

Complexity

The time complexity of Prim's algorithm depends on the data structures used:

• Using an adjacency matrix and searching: $O (|V|^2)$
• Using a priority queue (as in the implementation above) and adjacency list, Prim's algorithm runs in $O (|E| \log |V|)$, where $E$ is the number of edges and $V$ is the number of vertices.

This makes it very suitable for dense graphs.

Implementation

Here is a basic implementation of Prim's Algorithm in Python using a priority queue to select the minimum weight edge efficiently.

import heapq

def prim(graph, start):
    # graph is represented as a dictionary of dictionaries {node: {neighbor: weight, ...}, ...}
    mst = []  # List to store MST edges
    visited = set([start])
    edges = [(cost, start, to) for to, cost in graph[start].items()]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            for next_to, next_cost in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_cost, to, next_to))
    
    return mst

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 1, 'E': 1},
    'E': {'B': 4, 'D': 1, 'F': 1},
    'F': {'C': 5, 'E': 1}
}

# Computing the MST
mst = prim(graph, 'A')
print("Edges in the MST:", mst)

Output Analysis

This will generate a list of edges that are included in the MST, showing how the algorithm incrementally selects the lowest weight edges to construct the MST while ensuring no cycles are formed.

Reference and Useful Links

• Prim's Algorithm - GeeksForGeeks
• Minimum Spanning Tree on Wikipedia